import java.util.ArrayList;
import java.util.List;

public class Solution301 {
    List<String> res;

    public List<String> removeInvalidParentheses(String s) {
        res = new ArrayList<>();
        int left = 0, right = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else if (s.charAt(i) == ')') {
                if (left > 0) {
                    left--;
                } else {
                    right++;
                }
            }
        }
        dfs(s, 0, new StringBuilder(), left, right);
        return res;
    }

    void dfs(String s, int index, StringBuilder sb, int left, int right) {
        int t = sb.length();
        for (int i = index; i < s.length(); i++) {
            char c = s.charAt(i);
            if (i != index && c == s.charAt(i - 1)) {
                sb.append(c);
                continue;
            }
            if (left + right > s.length() - i) {
                sb.delete(t, sb.length());
                return;
            }
            if (left > 0 && c == '(') {
                dfs(s, i + 1, sb, left - 1, right);
            }
            if (right > 0 && c == ')') {
                dfs(s, i + 1, sb, left, right - 1);
            }
            sb.append(c);
        }
        if (left == 0 && right == 0) {
            if (isValid(sb)) {
                res.add(sb.toString());
            }
        }
        sb.delete(t, sb.length());
    }

    private boolean isValid(StringBuilder str) {
        int cnt = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                cnt++;
            } else if (str.charAt(i) == ')') {
                cnt--;
                if (cnt < 0) {
                    return false;
                }
            }
        }

        return cnt == 0;
    }
}
